package Leetcode.Dichotomy;

/**
 * @Author: kirito
 * @Date: 2024/4/11 14:26
 * @Description:
 * 丑数 III
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
 *
 * 丑数是可以被 a 或 b 或 c 整除的 正整数 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 3, a = 2, b = 3, c = 5
 * 输出：4
 * 解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。
 * 示例 2：
 *
 * 输入：n = 4, a = 2, b = 3, c = 4
 * 输出：6
 * 解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12... 其中第 4 个是 6。
 * 示例 3：
 *
 * 输入：n = 5, a = 2, b = 11, c = 13
 * 输出：10
 * 解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
 * 示例 4：
 *
 * 输入：n = 1000000000, a = 2, b = 217983653, c = 336916467
 * 输出：1999999984
 */

public class nthUglyNumber {
    /**
     * 既然已经确定了二分法作为切入点，关键问题来了，如何二分呢？
     *
     * 按照题意，所谓丑数是可以至少被a、b、c三者中的一者整除的，那么对于一个丑数X，我们能够确定它是第几个丑数吗？
     *
     * --答案显然是可以的，我们只需要计算X中包含了多少个丑数因子即可。
     *
     * 即只需要知道在[0,X]范围内,还有多少个丑数即可，而这些丑数，无非就是一些能被a或者b或者c所整除的数。
     *
     * 那么显然，我们直接用X/a、X/b、X/c就能计算出[0,X]范围内有多少数能被a或者b或者c整除，然后把它们加起来就是答案！
     *
     * 但是仔细思考一下，我们是不是重复计算了些什么？如果一个数既能被a整除，又能被b整除，那么实际上该数在先前的计算中就被重复计算了一次(分别是在计算X/a和X/b时)。
     *
     * --好吧，让我们思考所有可能的情况
     *
     * 1.该数只能被a整除 (该数一定是a 的整数倍)
     *
     * 2.该数只能被b整除 (该数一定是b 的整数倍)
     *
     * 3.该数只能被c整除 (该数一定是c 的整数倍)
     *
     * 4.该数只能被a和b同时整除 (该数一定是a、b最小公倍数的整数倍)
     *
     * 5.该数只能被a和c同时整除 (该数一定是a、c最小公倍数的整数倍)
     *
     * 6.该数只能被b和c同时整除 (该数一定是b、c最小公倍数的整数倍)
     *
     * 7.该数只能被a和b和c同时整除（该数一定是a、b、c的最小公倍数的整数倍）
     *
     * 所以，我们只需要分别计算以上七项就能得到结果了！让我们分别来看（用MCM+下标表示最小公倍数）：
     *
     * 情况1 = X/a - 情况4 - 情况5 - 情况7
     * 情况2 = X/b - 情况4 - 情况6 - 情况7
     * 情况3 = X/c - 情况5 - 情况6 - 情况7
     * 情况4 = X/MCM_a_b - 情况7
     * 情况5 = X/MCM_a_c - 情况7
     * 情况6 = X/MCM_b_c - 情况7
     * 情况7 = X/MCM_a_b_c
     *
     * 让我们整理上述方程后也就得到：
     *
     * sum(情况) = X/a + X/b + X/c - X/MCM_a_b - X/MCM_a_c - X/MCM_b_c + X/MCM_a_b_c
     *
     * 好了，现在也就得到了计算X中包含多少个丑数因子的方法了！
     *
     * 至于计算最小公倍数的方法，这里不多介绍，概括而言就是对于两个数a和b，它们的最小公倍数 = a*b/(a和b的最大公约数)，
     * 最大公约数可以通过辗转相除法得到
     *
     * 二分搜索
     *
     * 在得到了计算任意数中包含了多少个丑数因子的方法后，我们实际上只需要通过二分法，不断缩小边界范围，
     * 直到某个位置所对应的数恰好包含了n个丑数因子为止。
     *
     * 注意，通过二分法计算的答案并非是最终答案，因为可以有很多数同时包含有n个丑数因子！
     *
     * 比如第n个丑数是X，那么[X,X + min(a,b,c))这个半开区间内的所有数都同时包含n个丑数因子，
     * 我们通过二分法得到的答案也随机分布于这个区间中。而实际上我们只需要得到该区间的左端即可。
     * 处理方法很简单：假设我们得到的临时答案是K(K∈[X,X + min(a,b,c))),那么K - min(K%a,K%b,K%c) = X.
     * 也就是只需要把临时答案减去其与a、b、c三者中取余的最小值即可！
     * @param n
     * @param a
     * @param b
     * @param c
     * @return
     */
    public int nthUglyNumber(int n, int a, int b, int c) {
        int l = 1, r = Integer.MAX_VALUE;
        // 设置二分搜索的范围，l为最小可能丑陋数，r为最大可能丑陋数

        while (l < r) {
            int mid = l + (r - l) / 2;
            // 计算中间值
            if (check(mid, n, a, b, c)) {
                // 如果mid是可以被a、b、c中的一个或多个整除的第n个丑陋数，缩小搜索范围到左边
                r = mid;
            } else {
                // 如果mid不是第n个丑陋数，扩大搜索范围到右边
                l = mid + 1;
            }
        }
        // 当循环结束时，l指向的就是第n个丑陋数
        return r;
    }

    boolean check(int mid, int n, int a, int b, int c) {
        // 这个辅助函数用于检查mid是否是第n个丑陋数
        long ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c), abc = lcm(lcm(a, b), c);
        // 计算a、b、c两两的最小公倍数以及三个数的最小公倍数

        long cnt = (long)mid / a + mid / b + mid / c
                - mid / ac - mid / bc - mid / ab + mid / abc;
        // 计算小于等于mid的丑陋数的数量
        // 使用容斥原理计算，避免重复计数

        return cnt >= n;
        // 如果小于等于mid的丑陋数的数量大于等于n，则mid可能是第n个丑陋数
    }

    long gcd(long a, long b) {
        // 辅助函数，用于计算两个数的最小公倍数
        return b == 0 ? a : gcd(b, a % b);
    }

    long lcm(long a, long b) {
        // 辅助函数，用于计算两个数的最小公倍数
        return a / gcd(a, b) * b;
    }

}
